package Top_Interview_Questions_Review._002DFS;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/7 15:27
 * <p>
 * https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/
 *
 * 因为这个包是dfs的题,所以有几个题有dfs,bfs,并查集等多种方法。但是我第一遍写都只写dfs这一种方法
 *
 */
public class _0200 {


    public static void main(String[] args) {
        _0200 test = new _0200();
        char[][] grid1 = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}};
        int numIslands1 = test.numIslands(grid1);
        System.out.println(numIslands1);

        char[][] grid2 = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}};
        int numIslands2 = test.numIslands(grid2);
        System.out.println(numIslands2);
    }


    //这个递归是直接从grid[0][0]开始,把跟第一个1相连的1全替换为0。这样在后续递归的时候，就不用重复判断
    /*
     * 每次dfs的时候,都把跟第一个1(也就是相当于第一块岛屿)相连的1全替换为0。这样在后续递归的时候,
     * 就不用重复判断相同的岛屿。因为相连的岛屿除了第一个1,全都已经被替换成了0。所以只要发现新的1,
     * 就说明是新的一块岛屿。所以下面这个if也就可以理解了
       if (grid[r][c] == '1') {
             ++num_islands;
             dfs1(grid, r, c);
          }
     */
    public int numIslands1(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs1(grid, r, c);
                }
            }
        }

        return num_islands;
    }

    void dfs1(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';//用这个替代标记
        dfs1(grid, r - 1, c);
        dfs1(grid, r + 1, c);
        dfs1(grid, r, c - 1);
        dfs1(grid, r, c + 1);
    }

    /*-------------------------------------------------------------------------------------*/


    /*-------------------------------------------------------------------------------------*/

//    //           x-1,y
//    //  x,y-1    x,y      x,y+1
//    //           x+1,y
//    // 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是一个常见的技巧
//    private static final int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
//    // 标记数组，标记了 grid 的坐标对应的格子是否被访问过
//    private boolean[][] marked;
//    // grid 的行数
//    private int rows;
//    // grid 的列数
//    private int cols;
//    private char[][] grid;
//
//    public int numIslands(char[][] grid) {
//        rows = grid.length;
//        if (rows == 0) {
//            return 0;
//        }
//        cols = grid[0].length;
//        this.grid = grid;
//        marked = new boolean[rows][cols];
//        int count = 0;
//        for (int i = 0; i < rows; i++) {
//            for (int j = 0; j < cols; j++) {
//                // 如果是岛屿中的一个点，并且没有被访问过
//                // 就进行深度优先遍历
//                if (!marked[i][j] && grid[i][j] == '1') {
//                    count++;
//                    dfs(i, j);
//                }
//            }
//        }
//        return count;
//    }
//
//    // 从坐标为 (i,j) 的点开始进行深度优先遍历
//    private void dfs(int i, int j) {
//        marked[i][j] = true;
//        // 得到 4 个方向的坐标
//        for (int k = 0; k < 4; k++) {
//            int newX = i + directions[k][0];
//            int newY = j + directions[k][1];
//            // 如果不越界、没有被访问过、并且还要是陆地
//            if (inArea(newX, newY) && grid[newX][newY] == '1' && !marked[newX][newY]) {
//                dfs(newX, newY);
//            }
//        }
//    }
//
//    // 封装成 inArea 方法语义更清晰
//    private boolean inArea(int x, int y) {
//        // 等于号不要忘了
//        return x >= 0 && x < rows && y >= 0 && y < cols;
//    }
//
    /*-----------------------------------------我写的----------------------------------------*/
    int[][]  direct= {{-1,0},{1,0},{0,-1},{0,1}};
    //标记数组
    boolean[][] marked;
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0)
            return 0;

        int m = grid.length;
        int n = grid[0].length;

        int count = 0;
        marked = new boolean[m][n];
        for(int i =0;i < m;i++){
            for(int j=0;j < n;j++){
                if(!marked[i][j] && grid[i][j] == '1'){
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid,int i,int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || marked[i][j] || grid[i][j] == '0'){
            return;
        }
        marked[i][j] = true;
        for(int k = 0;k < direct.length;k++){
            int newX = i + direct[k][0];
            int newY = j + direct[k][1];
            dfs(grid,newX,newY);
        }
    }

    /*-------------------------------------------------------------------------------------*/


}
